package leetcode_2501_2600;

import java.util.*;

public class LeeCode_2503 {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(maxPoints(new int[][]{{1, 2, 3}, {2, 5, 7}, {3, 5, 1}}, new int[]{5, 6, 2})));
        System.out.println(Arrays.toString(maxPoints(new int[][]{{5, 2, 1}, {1, 1, 2}}, new int[]{3})));
    }
    private static int[] maxPoints(int[][] grid, int[] queries) {
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> grid[o[0]][o[1]]));
        queue.add(new int[]{0, 0});
        int[][] min = new int[m][n];
        for (int i = 0; i < m; i++) {
            min[i] = Arrays.copyOfRange(grid[i], 0, n);
        }
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        min[0][0] = grid[0][0];
        while (!queue.isEmpty()){
            int[] p = queue.poll();
            int x = p[0], y = p[1];
            if (vis[x][y]) {
                continue;
            }
            int out = Integer.MAX_VALUE;
            List<int[]> list = new ArrayList<>();
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n){
                    continue;
                }
                if (!vis[nx][ny]){
                    list.add(new int[]{nx, ny});
                    continue;
                }
                out = Math.min(out, min[nx][ny]);
            }
            out = out == Integer.MAX_VALUE ? 0 : out;
            min[x][y] = Math.max(min[x][y], out);
            vis[x][y] = true;
            queue.addAll(list);
        }
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] ints : min) {
            for (int j = 0; j < n; j++) {
                map.put(ints[j], map.getOrDefault(ints[j], 0) + 1);
            }
        }
        int sum = 0;
        for (Integer key : map.keySet()) {
            sum += map.get(key);
            map.put(key, sum);
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int q = queries[i];
            Integer key = map.lowerKey(q);
            ans[i] = key == null ? 0 : map.get(key);
        }
        return ans;
    }
}